/* 计数排序 */
function countSort(max, arr) {
    const buckets = new Array(max + 1).fill(0)

    for (let n of arr) {  buckets[n]++  }
/* 这就是计数排序和桶排最显著区别  这里是计算出每个区间的开始或结束下标，通过其前缀和的形式 */
    for( let i = 1; i< buckets.length; i++){
      buckets[i]+= buckets[i-1]
    }
/* 我想使用区间开始下标 因此在前缀和前面放个0 表示从0开始， 下一个区间就是从n开始，包含n */
buckets.unshift(0)    
const res = []
    for (let i = 0; i <arr.length; i++) {
        res[buckets[arr[i]]++]  = arr[i]
    }

    return res
}

function baseSort(nums){
    /* 低位最多是65536 -1  加1就进位了 */
    const  counts = new Array( 65536).fill(0)
    const temp = new Array( nums.length) ;

    for (let n of nums) {  
        // console.log(n & 65535)
        counts[n & 65535 ]++  }
    for (let i = 1; i< 65536; i++) {counts[i] +=counts[i-1]    }
    counts.unshift(0)
    // console.log( counts, 'counts')
    /* 没记录索引，借助额外空间，把刚才统计得到结果对号入座 */
    for (let i = 0; i < nums.length ; i++) {
        temp[counts[nums[i] & 65535]++] = nums[i]; 
    }
    console.log( temp)

    for(  let i = 0; i < 65536; i++){ counts[i] =0}
    counts.pop()
    /* 位移运算的优先级高于 位与运算 */
    for (let n  of temp ){ counts[(n & 0xffff0000 )>> 16]++ ;console.log((n & 0xffff0000 )>> 16) }
    for ( let i = 1; i < 65536; i++){ counts[i]+=counts[i-1] }
    counts.unshift(0)
    console.log( counts.filter(i => i), 'copunts')

    for( let i = 0; i< nums.length; i++){  nums[counts[ (temp[i] & 0xffff0000) >> 16 ]++] = temp[i]}

    return nums

}

function getRandArr(n) {
    const arr = []
    for (let i = 0; i < n; i++) {

        arr.push(Math.random() * 90 | 0);
    }
    return arr

}

let arr1 = [494767408,862126209,213511142,768240025,631263193,839199222,990848796,214568815,540853864,760724418,980162605,976743981,168965760,680875496,256709197,970953816,948680062,347254784,732201399,786249847,782805044,40906641,674241381,784330934,175502610,731105392,424650824,549764101,986090032,710542549,249208107,448419816,527708664,158499246,223421723,114552457,466978424,821491411,19614107,115389497,902211438,2644108,744489871,897895073,372311214,551142753,933294894,426217662,217504874,983488406,516890023,426853110,971124103];
baseSort(arr1)
console.log(  arr1)
